package com.zang.dp;

import io.github.vampireachao.stream.core.business.highlight.FoundWord;
import io.github.vampireachao.stream.core.business.highlight.HighlightHelper;
import io.github.vampireachao.stream.core.stream.Steam;

import java.util.List;

/**
 * @author ZVerify
 * @since 2022/11/24 19:50
 * @see <a href="https://leetcode.cn/problems/integer-break/">...</a>
 **/
public class 整数拆分 {

    public int integerBreak(int n) {

        int[] dp = new int[n+1];

        dp[2] = 1;

        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i-j; j++) {
                // 可以直接i*j 还有1*i 还有拆分多个逐一比较每个都遍历然后取最大值
                dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)) );
            }
        }
        return dp[n];
    }

}
